Algorithmic Lovász local lemma について

Words near each other

・ Algorithm design
・ Algorithm engineering
・ Algorithm March
・ Algorithme Pharma
・ Algorithmic art
・ Algorithmic complexity
・ Algorithmic complexity attack
・ Algorithmic composition
・ Algorithmic cooling
・ Algorithmic efficiency
・ Algorithmic game theory
・ Algorithmic inference
・ Algorithmic information theory
・ Algorithmic learning theory
・ Algorithmic logic
・ Algorithmic Lovász local lemma
・ Algorithmic mechanism design
・ Algorithmic Number Theory Symposium
・ Algorithmic probability
・ Algorithmic program debugging
・ Algorithmic regulation
・ Algorithmic skeleton
・ Algorithmic state machine
・ Algorithmic trading
・ Algorithmic version for Szemerédi regularity partition
・ Algorithmica
・ Algorithmically random sequence
・ Algorithmics
・ Algorithmics Inc.
・ Algorithms (journal)

Dictionary Lists

mini英和辞書

翻訳と辞書　辞書検索 [ 開発暫定版 ]

スポンサードリンク

Algorithmic Lovász local lemma ：ウィキペディア英語版

Algorithmic Lovász local lemma
In theoretical computer science, the algorithmic Lovász local lemma gives an algorithmic way of constructing objects that obey a system of constraints with limited dependence.
Given a finite set of ''bad'' events in a probability space with limited dependence amongst the ''A_i''s and with specific bounds on their respective probabilities, the Lovász local lemma proves that with non-zero probability all of these events can be avoided. However, the lemma is non-constructive in that it does not provide any insight on ''how'' to avoid the bad events.
If the events are determined by a finite collection of mutually independent random variables, a simple Las Vegas algorithm with expected polynomial runtime proposed by Robin Moser and Gábor Tardos〔.〕 can compute an assignment to the random variables such that all events are avoided.
==Review of Lovász local lemma==
(詳細はprobabilistic method to prove the existence of certain complex mathematical objects with a set of prescribed features. A typical proof proceeds by operating on the complex object in a random manner and uses the Lovász Local Lemma to bound the probability that any of the features is missing. The absence of a feature is considered a ''bad event'' and if it can be shown that all such bad events can be avoided simultaneously with non-zero probability, the existence follows. The lemma itself reads as follows:

Let $\mathcal = \$ be a finite set of events in the probability space Ω. For $A \in \mathcal$ let $\Gamma(A)$ denote a subset of $\mathcal$ such that $A$ is independent from the collection of events $\mathcal \setminus (\ \cup \Gamma(A))$ . If there exists an assignment of reals $x : \mathcal \rightarrow (0,1)$ to the events such that
: $) \leq x(A) \prod_ (1-x(B))$
then the probability of avoiding all events in $\mathcal$ is positive, in particular
: $) \geq \prod_{A \in \mathcal{A}} (1-x(A)).$

抄文引用元・出典: フリー百科事典『ウィキペディア（Wikipedia）』
■ウィキペディアで「Algorithmic Lovász local lemma」の詳細全文を読む

スポンサードリンク

翻訳と辞書 : 翻訳のためのインターネットリソース